\chapter{Inexact Solution Methods To Capacity Expansion Problem in Survivable
Networks }

\label{chap-six}
Multiple variations of exact solution approaches, using linear integer
programming and Benders decomposition methods were introduced in the previous
chapters. However, many real-life larg-sized service networks cannot be
addressed with the exact methods introduced, as they would be computationally
extensive. In this chapter we propose heuristics and meta-heuristics designed to
find near optimal feasible solutions within a reasonable computation time and
effort.
These methods are developed to address the large-sized networks more
efficiently.
These methods are all in a class of search methods called neighborhood search
heuristics and are still not gradient-free approaches, in the sense that we are
trying to use the problem's data and variable coefficients to perform a better search of the solution space. The downside of the approach, however, is that we
can no longer guarantee that the solution found is the optimal solution to the integer
programming model representing the capacity design and expansion problem in
survivable networks we provided in the previous chapters.

\section{Feasibility Check}
Given the current capacities, none to node demands and the effects of failure
scenarios on them, there is a chance that the decision maker would not be able to satisfy the
demands under all the failure scenarios. This happens, as the capacitiy
expansion decisions are limited in nature.
It is of high importance to discover if the SNCE-1 (Survivable Network
Capacity Expansion) is feasible, given the problem data, before going through
unnecessary computational effort. Here we introduce a simple heuristic
for checking the feasibility of the whole problem. Using this heuristic, not
only we are able to find out about the feasibility of the problem, but also if
the problem is in fact feasible it will give us an incumbent solution. Having an incumbent solution will significantly help the search
process in the later steps. We will discuss finding incumbent solutions more in
the follwoing sections.


%But the lower bound derived from this
%relaxation is very weak, and the gap between the lower bound derived and the
% upper bound is relatively large.

\subsection{Feasibility Test}
\paragraph{Lemma 3}
\textit{Suppose 
\begin{equation}
U_{e,\hat{l}}=\max_{l\in L_{e}}U_{e,l} \hspace{0.2mm},\hspace{1mm} \forall e \in E
\end{equation}\\
}
(with the same notation introduced in chapter \ref{chap-three}). \textit{Now let
$\hat{z}$ be a first stage solution to SNCE-1 such that 
\begin{equation}
\hat{z}_{e,\hat{l}}=1 \hspace{4mm}  \forall e \in E,\hspace{1mm} \text{and} \hspace{2mm} \hat{z}_{e,l}=0 \hspace{4mm} \forall l \in L_{e}\setminus\left\{\hat{l}\right\} \hspace{4mm} \forall e \in E
\end{equation} 
 if by using $\hat{z}$ all the sub-problems in SNCE-1-R can arrive at the
 optimal solution of 0, then SNCE-1 problem is feasible. If any of sub-the problems in 
 SNCE-1-R has an optiaml solution of greater  than 0, then SNCE-1 is infeasible.
 }\\
 \\
 Lemma 3 states that by choosing the maximum available capacity for all the
 links, if the network can satisfy the demands under all the failure scenarios, then
 the SNCE-1 problem is feasible. Otherwise, given the problem data, there is no
 decision alternative under which all node to node demands could be satisfied
 under all the failure scenarios.
 \paragraph{Example 1} Consider the network introduced as Example 4 in chapter
 3 ( see \fref{fig:hist3}) with the same travel demands, capacities and failure
 scenarios data provided in Tables \ref{tab:four} through \ref{tab:six}.
 
 \begin{figure}

\centering

\includegraphics[width=0.4\textwidth]{Chapter-3/figs/Net3}

\caption{The example network}

\label{fig:hist3}

\end{figure}
To do the Feasibility test, the candidate solution, which has the highest
capacity chosen for each link is formed as (17,21,9,5,31,25,10,50).
So the candidate solution to try for feasibility check is :
$z_{1,3}=z_{2,3}=z_{3,3}=z_{4,1}=z_{5,3}=z_{6,3}=z_{7,3}=z_{8,3}=1$. This will
result a feasible assignmet of flows in the network under all 5 failure
scenarios with a total cost of 131. The follow assignment is as represented in
table \ref{tab:one} ( only non-zero assignments are shown.)


\begin{table}

\caption{Finding a Feasible Set of Flow Variables in Example 1  }

\label{tab:one}

\begin{center}

\begin{tabular}{lcccc}

\toprule

 \textit{(Path)}  & \textit{(Origin-Destinatio)} &
 \textit{Failure Scenario} & \textit{Amount of Flow} &\\

\midrule

 
1 & 1 &  1 &  6.00 \\
1 &  1 &  2 & 9.02 \\
1 &  1 &  3 & 4.80 \\
1 &  1 &  4 & 3.60 \\
1 &  1 &  5 & 3.45 \\
2 &  1 &  2 & 2.98 \\
2 &  1 &  5 & 2.55 \\
5 &  2 &  1 & 5.00 \\
5 &  2 &  2 & 7.00 \\
5 &  2 &  3 & 2.50 \\
5 &  2 &  4 & 3.00 \\
5 &  2 &  5 & 5.50 \\
7 &  3 &  1 & 4.00 \\
7 &  3 &  2 & 7.60 \\
7 &  3 &  3 & 6.40 \\
7 &  3 &  4 & 8.40 \\
7 &  3 &  5 & 6.80 \\


\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}

\section{Optimality Gap}
Before begining the discussion of heuristics we like to introduce a measure that
is used to evaluate the quality of the non-optimal solutions. One of the
measures that is widely being used it the optimality gap.
 We define Optimality Gap as the difference between the current objective and
 the objective of the optimal solution ( if available) to the problem. When an optiaml solution is not available, we use the objective of the best available solution. Optimality gap in usually calculated using two
 measures:
 \textit{absolute objective gap} and \textit{relative objective gap}. These measures can be used when arriving at each solution to calculate how close we are to a theoritical best solution. For a
 theoritical best solution we will be using the bound provided by LP-Relaxation
 of the problem. We could use the gaps for two different reasons: Firstly, they
 can be used as a stopping criteria, that means at any given solution, if either
 one of the gaps is less than decision maker's threshold, we can stop the searching process.Secondly,the gap
 calculation can also be used when each of the algorithms end, to compare the
 quality of the solutions they have provided.\\
 



 \section{Start Heuristics} 
 Since solving mixed integer programming problems is NP-hard, finding any
 feasible solution to a MIP is in theory as hard as finding an optiaml one. In
 practice,however, there are some MIP instances for which finding a feasible
 solution is much easier than finding the optimal one. Here we try to take
 advantage of the structure of the problem and introduce rather easy-fast
 methods of finding a feasible solution, as a start point. Start heuristics aim
 at finding a feasible solution, mostly regardless of the quality of the solution, as early as possible in order to achieve a good performance in the overall optimization process. Although the solution might be far from optimal, it will provide a chance of having a start solution to be able to apply improvement heuristics on, while maintaining the feasiblity.
  
 \subsection{Costliest Feasible Solution}
 If the problem has a feasible solution, we are able to find a feasible solution
 to it using the method discussed in Lemma 3, i.e. by choosing the costliest
 option for each link. Needless to say, although this method guarantees finding a feasible
 solution, the solution will be the worst possible solution with regards to the
 objective function. Improvement heuristics can later be applied to this
 incumbent solution to possibly reduce the objective function.
 
 \paragraph{Example 2} Again consider the network used to describe Example 1.
 The costliest feasibile solution to this network is represented as
 $z_{1,3}=z_{2,3}=z_{3,3}=z_{4,3}=z_{5,3}=z_{6,3}=z_{7,3}=z_{8,3}=1$. This will result a feasible assignmet of flows in the network under all 5 failure
scenarios with a total cost of 138. The follow assignment is as represented in
table \ref{tab:one} ( only non-zero assignments are shown.)
 
\begin{table}

\caption{Finding a Feasible Set of Flow Variables in Example 2  }

\label{tab:Two}

\begin{center}

\begin{tabular}{lcccc}

\toprule

 \textit{(Path)}  & \textit{(Origin-Destinatio)} &
 \textit{Failure Scenario} & \textit{Amount of Flow} &\\

\midrule

 
1 & 1 &  1 &  6.00 \\
1 &  1 &  2 & 7.38 \\
1 &  1 &  3 & 4.80 \\
1 &  1 &  4 & 3.24 \\
1 &  1 &  5 & 3.45 \\
2 &  1 &  2 & 4.62 \\
2 &  1 &  4 & 0.36 \\
2 &  1 &  5 & 2.55 \\
5 &  2 &  1 & 5.00 \\
5 &  2 &  2 & 7.00 \\
5 &  2 &  3 & 2.50 \\
5 &  2 &  4 & 3.00 \\
5 &  2 &  5 & 5.50 \\
7 &  3 &  1 & 4.00 \\
7 &  3 &  2 & 7.60 \\
7 &  3 &  3 & 6.40 \\
7 &  3 &  4 & 8.40 \\
7 &  3 &  5 & 6.80 \\


\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}

 
 \subsection{Worst Case Scenario}
 Another approach to come up with a rather easy and fast feasible solution is to
 make up a fake worst case scenario and try to protect the network against that
 single scenario. 
 \textit {Lemma 4}
\textit{Suppose we create a failure scenario $\dot{s}$ such that}

\begin{equation}
\lambda_{e,\dot{s}}=\min_{s}\lambda_{e,s} \hspace{4mm}\forall e\in E
\label{eq:hist31}
\end{equation}
\textit{and}
\begin{equation}
\mu_{d,\dot{s}}=\max_{s}\mu_{d,s} \hspace{4mm}\forall d\in D
\label{eq:hist32}
\end{equation}
\begin{spacing}{1.5}\textit{and replace the second-stage problem of SNCE-1 by the capacity and demand constraints representing  $\dot{s}$. 
If the new problem is solved to feasibility, the solution will also be a
feasible solution to our original problem. If the new problem is
infeasible, no conclusions can be made.
}
The proof for Lemma 4 is intuitive. The new constraints formed by the fake
scenario are tighter than all the scenario-related constraints of original
problem and the new constraints will dominate the original problem's
constraints. There for the feasible region of the newly formed problem will be a
subset of the feasible region of the original problem. Hence, any feasible
solution to the new problem will also be feasible in our original problem. On
the other hand, if the new problem is infeasible, it does not mean the original
problem is infeasible as well. So this method will not necessarily yiled a
feasible solution, even if the original problem is in fact feasible. In other
words, the network might not be able to satisfy all the node to node demands
under this scenario, although it is able to do so under the real scenarios.
\end{spacing}
\vspace{5mm}
 
 
\paragraph{Example 3} Again consider the network used to describe Examples 1
and 2. The worst case scenario for this example is represented by 
 $(0.15, 0.42, 0.17, 0.36, 0.46, 0.32, 0.58, 0.50)$ as the links availability
 data and $(2.0, 1.4, 2.1 )$ as the demand data. Solving the problem with this
 single failure scenario will lead to the following results, with the optiaml
 objective of 73. Capacity expansion decisions and flow decesions are shown in
 Tables \ref{tab:Three} and \ref{tab:Four} ( only non-zero assignments are
 shown.)
 
 
 \begin{table}

\caption{Capacity Expansion Decisions  in Example 3- Non-Zero variables }

\label{tab:Three}

\begin{center}

\begin{tabular}{lc}

\toprule

 \textit{Link}  & \textit{Option}  \\ 
\midrule

 
2 &  3 \\
5 &  3  \\
6 &  3  \\
8 &  3  \\

\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}
 
\begin{table}

\caption{Flow Variables in Example 3 }

\label{tab:Four}

\begin{center}

\begin{tabular}{lcc}

\toprule

 \textit{Path}  & \textit{Origin-Destination} & \textit{Amount of Flow} \\
\midrule

 


1 &  1  & 0.90 \\
2 &  1  & 0.68 \\
3 &  1  & 10.42 \\
5 &  2  &  6.14 \\
6 &  2  & 1.52 \\
7 &  3  &  8.40\\


\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}
 
 
  \subsection{Rounding Heuristic}
 When LP relaxation to the SNCE-1 problem is solved, most probably at least one
 LP feasible, but IP infeasible (a solution with a fractional value for a binary
 varible) is produced. It seems natural if we try to round the fractional
 variables in order to get a feasible solution. In general, the possible number
 of roundings of an LP-feasible point doubles with every fractional variable. For a general
 problem it is not obvious to which direction each variable should be rounded. 
  For our problem, here  we propose a method which specifies for each binary
 variable which direction should be chosen for rounding to maintain the feasibilty of LP, while becoming IP feasible.
  Since our variables are binary, if every fractional variable is rounded up to 1, we will achieve IP feasibility
 but we will possibly lose the feasibility of our multiple choice constraints,
 ($\sum_{l\in l_{e}} z_{e,l_{e}} \leq 1 \hspace{3mm} \forall e=1,2,...,|E|$)
 since there will be more than one variable equal to 1. As the method
 proposed below does the rounding based on capacity data, we call it capacity
 based rounding. Here, like before, the assumption is that options are numbered in ascending order based on
 their capacity.
\subsubsection{Capacity Based Rounding Algorithm-CBRA}
\begin{enumerate}
\item Solve the LP-Relaxation of SNCE-1. Name the optimal solution as
$\hat{z}.$
\item For each link compute the total amount of the assigned capacity in the LP
relaxation as follows:
\begin{center}
    
   $\sum_{l\in L_{e}}U_{e,l}\hat{z}_{e,l_{e]}}=$ Total capacity
 assigned to link $e$.
  

   \end{center}
   \item For each link $e$, suppose $l_{e,NZmax}$ is the highest index of
   options of link $e$ such that $\hat{z}_{e,l_{e,NZmax}} > 0$ , then set
   $z_{e,l_{e,NZmax}}$=1 and all other $z_{e,l_{e}}$=0.
 \end{enumerate}
 \begin{spacing}{2.5}
 \end{spacing}

 
 The solution suggested by CBRA method is clearly integer feasible, as $z$
 variables are binary. To prove that the proposed solution provides a feasible
 solution to the original problem, we need to show that the capacity assigned to
 each link in this solution is greater than or equal to the one assigned by the
 LP relaxation. This will guarantee that the capacity and demand constrainst are
 also satisfied.\\
 \paragraph{\indent \textit \textbf{{Proof :}}}
 The capacity suggested by CBRA for link $e$ is $U_{e,l_{e,NZmax}}$, 
 since $\hat{z}_{e,l_{e,NZmax}}=1$. So, We need to show that this term is
 greater than $\sum_{l\in L_{e}}U_{e,l}\hat{z}_{e,l_{e]}}$ which is the total
 capacity assigned to this link by LP relaxation. So we should show 
 \begin{equation}
 U_{e,l_{e,NZmax}} \geq \sum_{l\in L_{e}}U_{e,l}\hat{z}_{e,l_{e]}}
 \end{equation}
  From the contraints we have $\sum_{l\in L_{e}}\hat{z}_{e,l_{e]}} \leq 1$ :
 \begin{spacing}{2.5}


 $\Rightarrow$ \indent $U_{e,l_{e,NZmax}}*(\sum_{l\in L_{e}}\hat{z}_{e,l_{e]}})
 \leq U_{e,l_{e,NZmax}}$
 
 \indent $\Rightarrow$ \indent
 $U_{e,l_{e,NZmax}}*\hat{z}_{e,1}+U_{e,l_{e,NZmax}}*\hat{z}_{e,2}+\ldots+U_{e,l_{e,NZmax}}*\hat{z}_{e,l_{e]}}
 \leq U_{e,l_{e,NZmax}}$
 
  \end{spacing}
  and as we previously assumed, the options are numbered in asending order based
  on their capacity, $U_{e,l_{e}} \leq U_{e,l_{e,NZmax}}$. Therefore we can
  substitute $U_{e,l_{e,NZmax}}$ term in the left side of the above inequality
  with smaller ($U_{e,l_{e}}$) terms.
  \begin{spacing}{2.5}
  \indent $\Rightarrow$ 
  $U_{e,1}*\hat{z}_{e,1}+U_{e,l_{e,2}}*\hat{z}_{e,2}+\ldots+U_{e,l_{e,NZmax}}*\hat{z}_{e,NZmax}\leq
  U_{e,l_{e,NZmax}}$
 
  \end{spacing}
  The left hand side of the inequality is the capacity assigned to link $e$ in
  the LP relaxation and the right hand is the one from CBRA heuristic.
  Therefore, the solution suggested by CBRA is also LP feasible, i.e, able to
  satisfy the demands and capacity constraints. As mentioned earlier, this
  method only helps to find a feasible solutions. Improvement heuristics which
  will be introduced later in the chapter can be used to possibly improve the
  quality of the solution.

 \paragraph{Example 4} Here we apply CBRA method on the same network studied in
 previous examples ( options in increasing cost order). LP relaxation
 gives the following results presented in Table \ref{tab:Five} for the capacity expansion decisions.
 To apply steps 2 and 3 we need to sum up the total value of the capacity
 assigned to each link and then choose the lowest cost option that has a
 capacity greater than the total capacity assigned to each link. The results of
 applying these steps are summerized in Table \ref{tab:Six}.
 

\begin{table}

\caption{Example 4-LP Relaxation Results for Capacity Expansion Variables }

\label{tab:Five}

\begin{center}

\begin{tabular}{lcc}

\toprule

 \textit{Link}  & \textit{Option} & \textit{Value} \\ 
\midrule

 
2 &  3 & 0.25628 \\
5 &  3 & 0.40720 \\
6 &  1 & 0.34524 \\
6 &  3 & 0.65476 \\
8 &  3 & 0.19111 \\

\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}


\begin{table}

\caption{Example 4- Applying steps 2 and 3 and making capacity expansion
decisions }

\label{tab:Six}

\begin{center}

\begin{tabular}{lcc}

\toprule

 \textit{Link}  & \textit{Total Capacity Assigned in LPR} & \textit{Option to
 Choose}
 \\
\midrule

        1    &   0.0000 & 1 \\
        2    &   5.3818 & 3 \\
        3    &   0.0000 & 1 \\
        4    &   0.0000 & 1 \\
        5    &   12.6232 & 3 \\
        6    &   17.7500 & 3 \\
        7    &   0.0000 & 1 \\
        8    &   9.5556 & 3 \\
                                         
        
\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}

 The choice of decisions suggested by CBRAM, as presented in Table \ref{tab:Six}
 leads to an objective value of 101, which is much better than the objectives
 found by previous start heuristics ( 138 and 131).
 
 
 \subsubsection{Capacity Based Rounding Algorithm-Modified (CBRAM)}
Here we do a small modification to the CBRAM method. In the original CBRA, we
always choose the capacity expansion option that has a value greater than the
total capacity assigned to the link by LPR. Here we are suggesting that if LPR
assigns a 0 value to a link, we do not need to choose an option for that link.
This small modification means not choosing an option for links 1,3,4 and 7 in
Table \ref{tab:Six}. Therefore the objective function of the suggested heuristic
solution reduces to 73, which is equal to the original objective solution of the
problem.This is a promising method, as we do not even need to use a mixed
integer programming solver.
 
 
 \subsection{Evaluating Start Heuristics}
 Here we introduce a few measures to enable us to compare the solutions
 suggested by start heuristics.
 \begin{enumerate}
 \item Time to arrive at the first feasible
 solution, as the user might like to have a solution early in the search
 process.
 \item Quality of the solution, which can be measured by a gap between the
 objective of the starting solution and the objective of the optimal solution,
 for cases where we have the optiaml.
 \item Solver Requirements, whether we need a solver to get the solution, and if
 yes what type of solvers are required.
  \end{enumerate}
  The results of comparing the start heuristics applied to the example network
  is summarized in Table \ref{tab:Seven}. As the example is over simplified, the
  time column does not convey much information in this case. 
  
  
  \begin{table}

\caption{Comapring Start Heuristics Applied to the Example Network }

\label{tab:Seven}

\begin{center}

\begin{tabular}{lccccc}

\toprule

 \textit{Method}  & \textit{Objective} &\textit{Absolute Gap} &
 \textit{Relative Gap} & \textit{CPU Time(sec)} & \textit{Solver Requirement}\\
\midrule

        Costliest    & 138   &65& 47.1\% &0.01 &No Solver  \\
        Worst Case   &  73  & 0&0.0\% &0.01&Mixed Integer Solver \\
        CBRA         & 101 & 28 &27.72\% &0.08 & Linear Solver \\
        CBRAM        &  73 & 0&0.0\% &0.07 & Linear Solver \\
           
        
\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}
  
  
 \section{Improvement Heuristics}
 \indent The goal of improvement heuristics is to form a new feasible solution
 of better objective value, out of one or more feasible solutions. This will become
 possible by knowing and taking advantage of the structure of the problem.\\
 In the following we will be introducing a few neigborhood search algorithms.
 These algorithms all start by using a known feasible solution and trying to
 find a new feasible solution in the neighborhood, i.e. by changing one or more
 variables at the same time leading to a better objective. A summery of the
 results of these algorithms applied to the example network studied through out
 this chapter is represented in Table XXX.
 
 \subsection{Neighborhood Search Algorithms - Moving From Feasibility to
 Optimality}
 
\indent In this section we will discuss three neighborhood search algorithms. In
 all of them it is assumed that we are starting from a feasible solution and
 moving to optimality, while maintaining the feasibility. In all of the
 following algorithms assume that without loss of generality, the options are
  numbered in asending order based on their capacity. Also, at each solution,
  for each link $e$ the non zero variable is indexed by $o$. Therefore for
   each link $e$ we have $z_{e,o}=1$ and $z_{e,l_{e}}=0$ if $l_{e}
 \neq o$ .
 
 \subsection{NS-1 Algorithm}
 \begin{enumerate}
   \item $n=1$ ; $i=o_{n}$  
   \item While $n\leq |E| $
   \item {\setlength\itemindent{15pt}While $i\geq 1$ do
  \item  Do the following change in the starting
  feasible solution:\\
 \indent {$(z_{n,i}=1 , z_{n,i-1}=0)$ $\Rightarrow$ 
$(z_{n,i}=0 , z_{n,i-1}=1)$}
\item Denote the solution formed in the previous step as $z_{imp}$. Check the LP
feasibility of $z_{imp}$. 
\begin{enumerate}
\item If it is LP feasible keep the change.
\item If it is not LP-feasible, go to step 7.
  \end{enumerate}
  \item $i=i-1$}

\item $n=n+1$

 \end{enumerate}
 The idea in NS-1 is to start with an already feasible solution and try to
 improve it step by step while maintaining the feasibility. It starts from the first
 link and checks to see if we can reduce the capacity one level from the
 capacity expansion alternative that is already chosen. If the problem is still
 feasible after capacity reduction, it tries reducing the capacity one more time
 and continues until reaching the last alternative for the current link, or
 becoming infeasible. Then moves on to the next link.\\
 The improvement in objective in each step is equal to $C_{n,i}-C_{n,i-1}$, if
 we are able to choose option $i-1$ instead of option $i$ for link $n$. The performance of the algorithm depends on the
sequence the links are chosen for improvement, i.e., starting from link $j$
might end up with a different result than starting from link $k$.
 
 
 \subsection{NS-2 Algorithm}
 \begin{enumerate}
   \item Let $A$ be the set of links : $A=\{e_{1},\ldots,e_{n}\}$, where $n$ is
   the size of the links set.
   \item \setlength\itemindent{15pt} while set $A$ is not empty
   \item \setlength\itemindent{25pt} For $k \in A $ do;
   \item {}\setlength\itemindent{15pt} $i=o_{k}$, where $o_{k}$ is the index of
   the non-zero option of link $k.$
   \item {}\setlength\itemindent{15pt} Do the following change :\\
 \indent {$(z_{k,i}=1 , z_{k,i-1}=0)$ $\Rightarrow$ 
$(z_{k,i}=0 , z_{k,i-1}=1)$}
\item Denote the solution formed in the previous step as $z_{imp}$. Check the LP
feasibility of $z_{imp}$. 
\begin{enumerate}
\item If it is LP feasible keep the change.
\item If it is not LP-feasible reverse the change and remove link $k$ from
set $A$. ( $A$=$A\setminus\{k\}$).
  \end{enumerate}
\end{enumerate}

The idea in NS-2 is very similar of the one discussed in NS-1. The difference
though, is in the way the links and options are traversed in the improvement
process. In NS-1 we do as much improvements as we can on a single link before
moving to the next link. In NS-2 however, one possible round of improvements are
done on each link, before moving to the next level of possible improvements. The
links for which no improvemenst could be done in each round are removed from the
list of candidate links for improvement in the subsequent rounds. The process
continues until no further improvements are available, i.e., the list of
candidate links for improvement is empty. The performance of the algorithm depends on the
sequence the links are chosen for improvement,i.e,starting from link $j$ might
end up with a different results than starting from link $k$. 
 

  \subsection{NS-3 Algorithm}
 \begin{enumerate}
   \item Let $A$ be the set of links : $A=\{e_{1},\ldots,e_{n}\}$, where $n$ is
   the size of the links set.
   \item \setlength\itemindent{15pt} While set $A$ is not empty
   \item \setlength\itemindent{25pt} $\forall{m \in A}$ do
   \item if $o_{e_{m}}=1$ then remove $e_{m}$ from $A$.
   \item calculate  $C_{m,o}-C_{m,o-1}$.(As a reminder $C_{i,j}$ is the cost of option $j$ of
  link $i$).
  \item Find $Max_{m}(C_{m,o}-C_{m,o-1})$, assume the maximum happens at index
$k$.
\item Do the following change :\\
 \indent {$(z_{k,i}=1 , z_{k,i-1}=0)$ $\Rightarrow$ 
$(z_{k,i}=0 , z_{k,i-1}=1)$}
\item Denote the solution formed in the previous step as $z_{imp}$. Check the LP
feasibility of $z_{imp}$. 
\begin{enumerate}
\item If it is LP feasible keep the change.
\item If it is not LP-feasible reverse the change and remove link $k$ from
set $A$. ( $A$=$A\setminus\{k\}$).
 \end{enumerate}
  \end{enumerate}

 In NS-3 we are trying to use the problem data in deciding on the order that
 improvements should be done in. In each step the link which makes the highest
 improvement in the objective is chosen. The links for which no improvements can
 be done(as they are already on their smallest capacity alternative, or any
 capacity reduction in them leads to infeasibility) are removed from the list of
 candidate links in each round.
 \\
 
 
 \subsection{Neighborhood Search Algorithms - Moving From Optimality to
 Feasibility}
 The algorithms discussed in the previous section all started at a feasible
 solution and moved toward reaching better objectives. Here we are presenting
 algorithms that start from a solution with a good objective, which is not
 necessarily feasible, and then move gradually toward feasibility. 
 
 \subsubsection{NS-4 Algorithm}
 
 \begin{enumerate}
   \item Let $A$ be the set of links : $A=\{e_{1},\ldots,e_{n}\}$, where $n$ is
   the size of the links set.

   \item Start at $z_{i,e}=0$ \hspace{5mm}  $\forall i , \forall e $
   \item Check for LP feasibility, if feasible then the problem is trivial and
   the optimal solution of all zeros is found.
   \item \setlength\itemindent{15pt} While A is not empty
   do;
    \item \setlength\itemindent{25pt} For $e$ in $A$ do;
   \item Assuming $i$ is the index of non-zero variable for link $e$, do the
   following change:\\
 \indent {$(z_{e,i+1}=0 , z_{e,i}=1)$ $\Rightarrow$ 
$(z_{e,i+1}=1 , z_{e,i}=0)$}
\item If $i$ is the highest index available for link $e$ then remove link $e$
from $A$.
   \item Check for LP feasibility, if feasible, break; a solution has been
   found.
   \item if infeasible, next $e$;
    
   
  \end{enumerate}
  In NS-4, we start from an all zero point. Then the algorithm starts by
  increasing capacity on links, step by step.After each change, the problem is
  re-evaluated for feasibility. If feasibility is not yet reached we move to the
  next link. The links for which the maximum capacity is reached are removed
  from the list of candidate links in each iteration. Here, the point is that we
  move from link to link, not from option to option. Meaning a whole round of
  one level improvements are done on all links, before considering a second
  improvement on a single link. By using this algorithm, if the problem is not
  infeasible, the break point (finding a solution) will definitely be reached
   before list $A$ is empty. If the problem is infeasible, list $A$ goes empty
   without finding a solution.
   
   
 
 \subsection{Comparing Heuristic Methods} 
 A comparison between the heuristics dicussed in this chapter, when applied to
   the example network is provided in Table \ref{tab:Eight}. We have also listed
   the LP Relaxation bases methods, as they can be used for improvement as well.
   For NS-4, as we started at an infeasible solution of all zeros, we were able
   to achieve a feasible solution, but the quality of that solution was not as
   good as the solutions found by other methods.
    One more noteworthy fact is that these method can be combined and used as
    hybrid methods, as the specific structure of each problem allows.
 \begin{table}

\caption{Comapring Heuristics Applied to the Example Network }

\label{tab:Eight}

\begin{center}

\begin{tabular}{lccccc}

\toprule

 \textit{Method}  & \textit{Start}  & \textit{Final Solution}
 &\textit{Improvement} & \textit{Final Relative Gap} & \textit{CPU Time(sec)} \\
\midrule

        NS-1    & 138 &107& 29.0\% &31.7\%& 0.2 \\
        NS-2   &  138 & 107&29.0\% &31.7\%& 0.48\\
        NS-3    & 138 &88& 56.8\% &17.04\% &0.62  \\
        NS-4   &  0 & 138& N/A &47.1\% &1.85\\
        CBRA    & 138 & 101 & 27.0\% &27.7\% &0.08   \\
        CBRAM    &138    &  73 &47.1\% &0&0.07  \\
           
        
\midrule

\bottomrule

\end{tabular}

\end{center}

\end{table}
 
  
 
 
 
 %So at each step, if the objective at the current solution is called
 % $Obj_{imp}$ and optimal objective of the problem is called $Obj_{opt}$ we will have:
 %\begin{center}
 %$Obj_{LP-Relaxation} \le Obj_{opt} \le Obj_{imp} $
 %\end{center}
 %The gaps are calculated as follows:\\
 
 %Absolute Objective Gap= $Obj_{imp}-Obj_{LP-Relaxation}$\\
 %Relative Objective Gap=
 % $(Obj_{imp}-Obj_{LP-Relaxation})/Obj_{LP-Relaxation}$\\
 
 
  
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 

 
 

